#include <stdio.h>
#include <malloc.h>
#include <iostream>
#include <stack>
#include <queue>

using namespace std;

// 线性表
typedef struct ListNode{
    int data;
    struct ListNode* next;
}ListNode,*List;

ListNode* newListNode(int data) {
    ListNode* node = (ListNode*) malloc(sizeof(ListNode));
    node->data = data;
    return node;
}

ListNode* CreateList() {
    List list = (ListNode*)malloc(sizeof(ListNode));

    List head = list;
    int number = 0;
    while(scanf("%d",&number) && number != -1) {
        ListNode* node = (ListNode*)malloc(sizeof(ListNode));
        node->data = number;
        node->next = NULL;

        list->next = node;
        list = node;
    }

    return head->next;
}

void PrintList(List list) {
    for(ListNode* p = list;p != NULL; p = p->next) {
        printf("%d ",p->data);
    }
}

typedef struct  {
    int element[10];
    int length;
}*SeqList,SL;

SeqList CreateSeqList(int n) {
    SeqList list = (SeqList) malloc(sizeof (SL));
    list->length = n;
    for (int i = 0; i <n; ++i) {
         scanf("%d",&list->element[i]);
    }
    return list;
}

// 树
typedef struct TNode{
    int data;
    struct TNode* leftChild;
    struct TNode* rightChild;
    int leftTag;
    int rightTag;
    int layer;
}TreeNode,*Tree;

TreeNode* newTreeNode(int data) {
    TreeNode* node = (TreeNode*) malloc(sizeof(TreeNode));
    node->data = data;
    node->rightChild = NULL;
    node->leftChild = NULL;
    return node;
}

TreeNode* CreateTree() {
    /*
    *       1
    *      / \
    *     2   3
    *        / \
    *       4   5
    * */
    TreeNode* treeNode1 = newTreeNode(1);
    TreeNode* treeNode2 = newTreeNode(2);
    TreeNode* treeNode3 = newTreeNode(3);
    treeNode1->leftChild = treeNode2;
    treeNode1->rightChild = treeNode3;
    TreeNode* treeNode4 = newTreeNode(4);
    TreeNode* treeNode5 = newTreeNode(5);
    treeNode3->leftChild = treeNode4;
    treeNode3->rightChild = treeNode5;
    return treeNode1;
}

TreeNode* CreateSearchTree() {
    /*
    *       5
    *      / \
    *     1   7
    *        / \
    *       6   8
    * */
    TreeNode* treeNode1 = newTreeNode(5);
    TreeNode* treeNode2 = newTreeNode(1);
    TreeNode* treeNode3 = newTreeNode(7);
    treeNode1->leftChild = treeNode2;
    treeNode1->rightChild = treeNode3;
    TreeNode* treeNode4 = newTreeNode(6);
    TreeNode* treeNode5 = newTreeNode(8);
    treeNode3->leftChild = treeNode4;
    treeNode3->rightChild = treeNode5;
    return treeNode1;
}

// 图
typedef struct ArcNode{ // 弧边信息
    int adj; // 当前弧对应可以到达的顶点， 比如弧为1-4 则to为4
    struct ArcNode *next; // 下一条弧的信息
}ArcNode;

typedef struct VertexNode{ // 顶点信息
    int data; // 当前顶点的值
    ArcNode* firstArc; // 所有弧的信息，用链表形式存储。
}VertexNode;


typedef struct{
    VertexNode* vertex[10];// 顶点信息,每个顶点信息里存着能到达的其他顶点
    int vexnum,arcnum; // 总顶点个数以及弧边个数.
}*Graph,G;

typedef struct{
    bool map[10][10];
    int vexnum,arcnum; // 总顶点个数以及弧边个数.
}*GraphMap,G2;

Graph CreateGraph() {
    /*
     *  1  - 2 - 3
     *   \  /
     *     4
     * */
    Graph g = (Graph) malloc(sizeof(G));
    g->arcnum = 6;
    g->vexnum = 3;
    // 1
    VertexNode* node1 = (VertexNode*) malloc(sizeof(VertexNode));
    node1->data = 1;
    // 1-2
    ArcNode* arc12 = (ArcNode*) malloc(sizeof(ArcNode));
    arc12->adj = 2;
    node1->firstArc = arc12;
    // 1-4
    ArcNode* arc14 = (ArcNode*) malloc(sizeof(ArcNode));
    arc14->adj = 4;
    arc14->next = NULL;
    arc12->next = arc14;
    g->vertex[1] = node1;
    // 2
    VertexNode* node2 = (VertexNode*) malloc(sizeof(VertexNode));
    node2->data = 2;
    // 2-3
    ArcNode* arc23 = (ArcNode*) malloc(sizeof(ArcNode));
    arc23->adj = 3;
    node2->firstArc = arc23;
    // 2-4
    ArcNode* arc24 = (ArcNode*) malloc(sizeof(ArcNode));
    arc24->adj = 4;
    arc23->next = arc24;
    // 2-1
    ArcNode* arc21 = (ArcNode*) malloc(sizeof(ArcNode));
    arc21->adj = 1;
    arc21->next=NULL;
    arc24->next = arc21;
    g->vertex[2] = node2;
    // 3
    VertexNode* node3 = (VertexNode*) malloc(sizeof(VertexNode));
    node3->data = 3;
    // 3-2
    ArcNode* arc31 = (ArcNode*) malloc(sizeof(ArcNode));
    arc31->adj = 2;
    arc31->next=NULL;
    node3->firstArc = arc31;
    g->vertex[3] = node3;
    // 4
    VertexNode* node4 = (VertexNode*) malloc(sizeof(VertexNode));
    node4->data = 4;
    // 4-1
    ArcNode* arc41 = (ArcNode*) malloc(sizeof(ArcNode));
    arc41->adj = 1;
    node4->firstArc = arc41;
    // 4-2
    ArcNode* arc42 = (ArcNode*) malloc(sizeof(ArcNode));
    arc42->adj = 2;
    arc42->next = NULL;
    arc41->next = arc42;
    g->vertex[4] = node4;
    return g;
}


void visit(int data) {
    printf("%d ",data);
    return;
}
// 队列
void initQueue(queue<int>  &queue) {
    return ;
}

void initTreeQueue(queue<TreeNode*>  &queue) {
    while(!queue.empty()) {
        queue.pop();
    }
    return ;
}

void enterQueue(queue<int> &queue,int data) {
    queue.push(data);
}

void enterTreeQueue(queue<TreeNode*> &queue,TreeNode* bt) {
    queue.push(bt);
}

void deleteQueue(queue<int> &queue,int* data){
    *data = queue.front();
    queue.pop();
}

TreeNode* deleteTreeQueue(queue<TreeNode*> &queue) {
    TreeNode * p = queue.front();
    queue.pop();
    return p;
}

bool EmptyQueue(queue<int> &queue) {
    return queue.empty();
}

bool EmptyTreeQueue(queue<TreeNode*> &queue) {
    return queue.empty();
}

// 哈希表

typedef struct{
    int key[10];
    int hash;
}*HashTable,H;

typedef struct LinkedNode {
    int data;
    LinkedNode* next;
}LinkedNode;

typedef struct{
    LinkedNode* key[10];
    int hash;
}*LinkedHashTable,LH;

// 栈
void initStack(stack<int> &stack) {
    while(!stack.empty()) {
        stack.pop();
    }
    return ;
}

void enterStack(stack<int> &stack,int data) {
    stack.push(data);
}

void deleteStack(stack<int> &stack,int* data){
    *data = stack.top();
    stack.pop();
}

bool EmptyStack(stack<int> &stack) {
    return stack.empty();
}

// 字符串
typedef struct S{
    ListNode* head;
    char ch[20];
    int length;
}*SString,S;

typedef struct S1{
    ListNode* head;
}LKString,S1;

SString CreateSString(char* ch,int length) {
    SString s = (SString) malloc(sizeof(S));
    s->length = length;
    for (int i = 0; i < length; ++i) {
        s->ch[i] = ch[i];
    }
    return s;
}